1. Field of the Invention
This invention generally relates to compressing and decompressing data, and more particularly, the invention relates to rateless compression and decompression of non-binary sources in a distributed compression environment.
2. Background Art
Distributed compression involves the compression of correlated data sources wherein the encoder for a source does not have access to complete information about the other sources. One embodiment of distributed compression is the scenario wherein the encoder has to compress a data source (hereafter simply termed “source) when the decoder has access to a correlated data source (hereafter termed “side-information”), and the encoder does not have access to the side-information. In general, this side-information may arise from decoding correlated data sources encoded and transmitted by other encoders. The amount of compression that can be achieved in this case depends, in general, on the degree to which the source and side-information are correlated.
Rateless codes refer to codes used for transmitting information (either for compression, or for protecting the data from channels, or for other reasons) which can be decoded at multiple rates at the decoder, depending on necessity. For example, an exemplary rateless channel code may be one wherein if the number of channel errors is low, the decoder can decode and recover the source data from a rate, say R1 bits of the codeword, and if the number of channel errors is high, the decoder can decode and recover the source data from a larger rate, say R2 bits of the same codeword. As another example, an exemplary distributed compression code may be one wherein if the correlation between source and side-information correlation is high, the decoder can decode and recover the source data from a rate, say R1 bits of the codeword, and if the if the correlation between source and side-information correlation is low, the decoder can decode and recover the source data from a larger rate, say R2 bits of the same codeword. The advantage of using a rateless code is that the same code can be used to allow source recovery in varying conditions, with the decoder simply choosing to receive a data rate which is adapted to the conditions. This is useful when transmission conditions are not known a-priori or when these change with time. Rateless codes are also useful when a transmitter is multicasting to multiple receivers, each with different conditions. In another embodiment, the encoder learns of the transmission condition immediately prior to transmission, and decides the rate of transmission at that time. In this case, rateless codes are advantageous because the same code can be used with several different transmission conditions; thus, the number of codes which need to be stored at the encoder for use can be considerably reduced.
Rateless coding has recently received considerable attention and a number of rateless codes have been developed for binary sources. For example, rateless codes are disclosed in “Rate-adaptive distributed source coding using low-density parity-check codes” (Varodayan, et al.) (in Proc. Asilomar Pacific Grove, Calif., November 2005); U.S. patent application publication no. US 2006/0156181 A1, for “Method for puncturing an LDPC channel code” (Ha, et al.); U.S. patent application publication no. US 2008/0320363 A1 for “Method and apparatus for rateless source coding with/without decoder side information” (He, et al.); and “On Rate-adaptivity of non-binary LDPC codes”, (Kline, et al.) (Proc. International Symposium on Turbo Codes & Related Topics, September 2008).
Varodayan, et al. describes how correlation adaptivity can be achieved by progressively sending accumulated syndromes. However, these codes are inefficient in that the performance of these codes is away from the compression limit. The method in Ha, et al. describes how binary ldpc codes can be punctured to achieve rate-adaptivity in the channel coding sense. Ha, et al. consider the channel coding problem and do not address how their methods can be applied for distributed compression.
The work in He, et al. considers puncturing variable nodes to achieve correlation adaptivity, however their solution only considers a simple approach wherein punctured variable nodes are punctured entirely, that is all bits in their binary representation, which is not best in terms of performance. The work in Kline, et al. considers bitwise puncturing of nonbinary ldpc codes. Kline, et al. show the benefits of puncturing a nonbinary ldpc code bitwise, however their work only applies to binary channels. Further, they do not address how bitwise puncturing can be applied for compression of distributed sources.